package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class MinimumInRotatedArray {

  @Test
  public void test() {
    System.out.println(minNumberInRotateArray(new int[] {3, 4, 5, 1, 2}));
    System.out.println(minNumberInRotateArray(new int[] {2, 3, 4, 5, 1}));
    System.out.println(
        minNumberInRotateArray(
            new int[] {
              6501, 6828, 6963, 7036, 7422, 7674, 8146, 8468, 8704, 8717, 9170, 9359, 9719, 9895,
              9896, 9913, 9962, 154, 293, 334, 492, 1323, 1479, 1539, 1727, 1870, 1943, 2383, 2392,
              2996, 3282, 3812, 3903, 4465, 4605, 4665, 4772, 4828, 5142, 5437, 5448, 5668, 5706,
              5725, 6300, 6335
            }));
  }

  public int minNumberInRotateArray(int[] array) {
    if (array.length == 0) {
      return 0;
    }

    int start = 0, end = array.length - 1;

    while (end - start != 1) {
      int mid = (start + end) / 2;
      if (array[mid] >= array[start]) {
        start = mid;
      }

      if (array[mid] <= array[end]) {
        end = mid;
      }
    }

    return array[end];
  }
}
